public class test {
    class Solution {
        List<String> res = new ArrayList<>();
        Map<String,Map<String,Integer>> map = new HashMap<>();
        public List<String> findItinerary(List<List<String>> tickets) {
            Map<String,Integer> tmp;
            for(List<String> t:tickets){
                if(map.containsKey(t.get(0))){
                    tmp = map.get(t.get(0));
                    tmp.put(t.get(1),tmp.getOrDefault(t.get(1),0)+1);
                }else{
                    tmp = new TreeMap<>();
                    tmp.put(t.get(1),1);
                }
                map.put(t.get(0),tmp);
            }
            res.add("JFK");
            backTracking(tickets.size());
            return res;
        }
        private boolean backTracking(int ticketNum){
            if(ticketNum+1 == res.size()){
                return true;
            }
            String last = res.getLast();
            if(map.containsKey(last)){
                for(Map.Entry<String,Integer>target:map.get(last).entrySet()){
                    int count = target.getValue();
                    if(count>0){
                        res.add(target.getKey());
                        target.setValue(count-1);
                        if(backTracking(ticketNum)){
                            return true;
                        }
                        target.setValue(count);
                        res.removeLast();
                    }
                }
            }
            return false;
        }
    }
}
